/*
 * @lc app=leetcode.cn id=76 lang=cpp
 *
 * [76] 最小覆盖子串
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> need(128, 0);       // 记录每个字符还需要的数量
        int needSum = 0;                // 记录需要字符的总数

        // 统计字符串 t 中需要的元素
        for (char c : t) {
            need[c]++;
            needSum++;
        }

        int left = 0;       // 左指针
        int right = 0;      // 右指针
        int start = 0;      // 记录最小窗口的开始下标
        int size = INT_MAX; // 记录最小窗口的长度

        while (right < s.length()) {
            // 扩展窗口，将 s[right] 加入窗口
            if (need[s[right]] > 0) needSum--;
            need[s[right]]--;

            // 判断是否已经包含所有字符
            if (needSum == 0) {
                // 缩减窗口，将 s[left] 移除窗口
                while (left <= right && need[s[left]] < 0) {
                    need[s[left]]++;
                    left++;
                }
                if (right - left + 1 < size) {
                    start = left;
                    size = right - left + 1;
                }
                // 记录最小窗口后，再次缩减窗口
                need[s[left]]++;
                needSum++;
                left++;
            }
            right++;
        }
        
        return (size == INT_MAX) ? "" : s.substr(start, size);
    }
};
// @lc code=end

